package org.algorithm.二师兄.数组.三月.第四周;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author zhx
 * @version 1.0
 * @date 2022/03/24 8:32 PM
 * @description:  周四作业
 *
 *
 * url :  https://leetcode-cn.com/problems/n-queens/
 */
public class N皇后 {

    static List<List<String>> ans=new ArrayList<List<String>>();

    public static void main(String[] args) {
        System.out.println(solveNQueens(4));

    }


    public static List<List<String>> solveNQueens(int n){
        int[] cur=new int[n];
        //cur数组表示0到 n-1行 中每行'Q'所处的列数
        //例如：cur[i]=j表示第i行的'Q'在第j列
        Arrays.fill(cur,-1);

        //三行，分别表示列冲突，左、右斜对角线冲突
        //因为是逐行放置的，没有行冲突了
        int[][] res=new int[3][2*n+1];

        dfs(res,0,cur,n);
        return ans;
    }

    /**
     *  递归处理
     */
    public static void dfs(int[][] res,int row,int[] cur,int n){
        //row表示行，row==n表示逐行放置全部放完，没有冲突即满足题目要求
        if(row==n){
            List<String> q=getString(cur);
            ans.add(q);
            return ;
        }

        //这里可以用树来理解，一层一层的，n个分支
        for(int i=0;i<n;i++){
            //这里res[2][i-row+n]之所以加n是防止出现负数，不好判断
            if(res[0][i]==0&&res[1][i+row]==0&&res[2][i-row+n]==0){

                //修改辅助变量
                cur[row]=i;
                res[0][i] = res[1][i+row] = res[2][i-row+n]=1;

                //向下递归
                dfs(res,row+1,cur,n);

                //将修改过的辅助变量更改回去
                cur[row]=-1;
                res[0][i] = res[1][i+row] = res[2][i-row+n]=0;
            }

        }
    }

    //将满足要求的集合返回
    public static List<String> getString(int[] cur){
        List<String> list=new ArrayList<String>();
        for(int i=0;i<cur.length;i++){
            char[] ch=new char[cur.length];
            Arrays.fill(ch,'.');
            ch[cur[i]]='Q';
            list.add(String.valueOf(ch));
            //注意区别
            //char[] -> String  :   String.valueOf(char[]);
            //String(s) -> char[]  :   s.toCharArray();
        }
        return list;
    }
}
